// Copyright 2011 Jefferson Willian
// willmont7@gmail.com

/* Estrutura para as arestas */
typedef struct edge {
  int orig;
  int dest;
  int weight;
}edge;

/* Algoritmo de Bellman-Ford   return false -> ciclo negativo        */
bool bellmanFord(vector<edge> edges, int dist[], int n, int m, int x = 0) {
  /* Condicao de parada de processo */
  bool stop;

  /* Seta valores iniciais para a matriz de distancia */
  for (int i = 0;i < n;i++)
    dist[i] = INF;
  dist[x] = 0;

  /* Processa todas as arestas enquanto houver atualizacoes */
  for (int i = 0;i < n;i++) {
    stop = true;
    for (int j = 0;j < m;j++)
      /* Verifica se utilizar a aresta 'j' eh a melhor opcao */
      if (dist[edges[j].orig] + edges[j].weight < dist[edges[j].dest]) {
        dist[edges[j].dest] = dist[edges[j].orig] + edges[j].weight;
        stop = false;
      }
    if (stop)
      break;
  }

  /* Deteccao de ciclo negativo:                             */
  /* Se houver mais alguma atualizacao a ser feita entao     */
  /* o grafo tem ciclo negativo                              */
  for (int j = 0;j < m;j++)
    if (dist[edges[j].orig] + edges[j].weight < dist[edges[j].dest])
      return false;

  return true;
}
